1. Field of the Invention
This invention relates to a straight line coordinates generator, and more particularly to a device which generates coordinates for a group of lattice points to simulate a straight line connecting two points.
2. Description of the Prior Art
The raster scan type graphic display device using a CRT monitor performs some basic operations to write a straight line connecting two points on the screen. The CRT monitor shoots an electron beam on the fluorescent screen to lighten predefined lattice points. Therefore, the raster scan type CRT monitor is principally limited to use of the predefined lattice points along its horizontal and vertical scan lines to generate a straight line between the two points, by defining the group of lattice points which must be lightened. When the CRT monitor displays a straight line, defined by the equation y=(Y/Z)x+a, connecting two points P.sub.0 and P.sub.n, it needs to simulate the line by continuously lightening the lattice points closest to the actual line. Therefore, the monitor must be provided with all of the coordinates of the group of lattice points to lighten in order to simulate the actual line.
In general, a secondary coordinates face is considered to have a group of lattice points spaced a constant one unit distance from each other. A simulated lattice point has a position x=x.sub.k on the line which is the nearest lattice point position corresponding to the actual position x=x.sub.k on the line y=(Y/X)x+a within the group of lattice points on the Y axis in the position x=x.sub.k. Therefore, as shown in FIG. 1 to simulate position Q on the corresponding line y=(Y/X)x+a to the position x=x.sub.k, the lattice point P.sub.k (x.sub.k, y.sub.k) must be selected from one of the two points P or P' whichever is nearest to the position Q on the Y axis. When the position Q is closer to the point P it becomes the simulated point P.sub.k, while when the position Q is closer to the point P', it becomes the simulated point P.sub.k. If the Y coordinate of the position Q is y and if the Y coordinates of the two points P and P' are n and n+1 respectively wherein n is an integer, the Y coordinate y.sub.k of the lattice point P.sub.k (x.sub.k, y.sub.k) to simulate the position Q on the line y=(Y/X)x+a corresponding to the line x=x.sub.k is determined by the following equations. EQU if n.ltoreq.y&lt;n+1/2 y.sub.k =n (1) EQU if n+1/2.ltoreq.y.ltoreq.n+1 y.sub.k =n+1 (2)
The above equations define that the simulated point P.sub.k will be the point P if the position Q is between the point P and a point midway between the points P and P', so called the comparative point, and that the simulated point P.sub.k will be the point P' if the position Q is between the point P' and the comparative point. In FIG. 1 it is apparent that the point P' becomes the simulated point P.sub.k.
A more detailed method to define each coordinate (x.sub.k, y.sub.k) of the group of the lattice points [P.sub.k (k=1, 2, . . . , n-1)] simulating the line y=(Y/K)x+a(0.ltoreq.Y/K.ltoreq.1) to connect the given two points P.sub.0 and P.sub.n will be explained hereinafter. If the slope Y/X is defined such that 0.ltoreq.Y/x.ltoreq.1, the Y coordinate of the next lattice point to the previously defined lattice point on the Y axis (assuming the X coordinate of the next lattice point is a positive one unit greater than the X coordinate of the previously defined lattice point) will be either equal to or will be one unit greater than the Y coordinate of the previously defined lattice point. Namely, if the coordinates of the previously defined lattice point are (x.sub.(k-1), y.sub.(k-1)), the coordinates (x.sub.k, y.sub.k) of the next lattice point P.sub.k are one of the following set of coordinates: EQU x.sub.k =x.sub.(k-1) +1, y.sub.k =y.sub.(k-1) ( 3) EQU x.sub.k =x.sub.(k-1) +1, y.sub.k =y.sub.(k-1) +1 (4)
If any coordinate of the group of the lattice points which simulate the line requires movement along the X axis in the negative direction, the sign may be changed to minus instead of plus.
The following explanation herein assumes the lattice points will only require movement along the X axis in the positive direction. The next lattice point P.sub.k to be required is on the Y axis whose X coordinate is x=x.sub.k. If the Y coordinate has a true value f.sub.k on the line at x=x.sub.k, it might satisfy the equation y.sub.(k-1) .ltoreq.f.sub.k .ltoreq.y.sub.(k-1) +1. The Y coordinate y.sub.(k-1) of the new lattice point P.sub.(k-1) corresponds to the n of the equations (1) and (2), and the f.sub.k also corresponds to the y. Instead of the equations (1) and (2) it can also be expressed as follows: EQU if y.sub.(k-1) .ltoreq.f.sub.k .ltoreq.y.sub.(k-1) +1/2 y.sub.k =y.sub.(k-1) ( 5) EQU if y.sub.(k-1)+1/2.ltoreq.f.sub.k .ltoreq.y.sub.(k-1) +1 y.sub.k =y.sub.(k-1) +1 (6)
As explained above, where the f.sub.k satisfies the equation y.sub.(k-1) .ltoreq.f.sub.k .ltoreq.y.sub.(k-1) +1, it is necessary to know whether f.sub.k is smaller or larger than y.sub.(k-1) +1/2 in order to determine the Y coordinate of the point P.sub.k. EQU if f.sub.k &lt;y.sub.(k-1) +1/2 y.sub.k =y.sub.(k-1) ( 7) EQU if f.sub.k .ltoreq.y.sub.(k-1) +1/2 y.sub.k =y.sub.(k-1) +1 (8)
Now if the term gk is introduced as follows: EQU g.sub.(k-1) =y.sub.(k-1) +1/2 (9)
Then the equations (7) and (8) become EQU if f.sub.k &lt;g.sub.(k-1) y.sub.k =y.sub.(k-1) ( 10) EQU if f.sub.k .ltoreq.g.sub.(k-1) y.sub.k =y.sub.(k-1) +1 (11)
The term g.sub.(k-1) is called the comparative value of the comparative point C.sub.k at x=x.sub.k.
It is apparent as mentioned above that if it is necessary to generate all of the coordinates (x.sub.k, y.sub.k) of the group of the lattice points [P.sub.k (k=1, 2 . . . n-1)] to simulate the line y=(Y/X)x+a(0.ltoreq.Y/X.ltoreq.1) connecting the given two points P.sub.0 and P.sub.n, the value f.sub.k of the Y coordinates on the line at x=x.sub.k and the comparative value g.sub.(k-1) of the comparative point C.sub.k at x=x.sub.k may be compared to test if f.sub.k is larger or smaller than g.sub.(k-1). It is apparent herein from the equation (9) that the comparative value g.sub.(k-1) is equal to the value of the Y coordinate y.sub.(k-1) of the previous simulated lattice point P.sub.(k-1) with 1/2 added to it.
In view of the aforementioned explanation, the determination of the straight line coordinates, by the prior art will be discussed hereunder. For example, the coordinates (x.sub.k, y.sub.k) of a group of lattice points [P.sub.k (k=1, 2 . . . 5)] to simulate a line represented by the equation y=(1/3)x connecting two points P.sub.0 (0, 0) and P.sub.6 (6, 2) may be required. The following Table 1 shows the values of the x.sub.k, y.sub.k, f.sub.k, and g.sub.k from the start point P.sub.0 (0, 0) to the point P.sub.6 (6,2), adding one to the X coordinates step by step.
TABLE 1 ______________________________________ k 0 1 2 3 4 5 6 ______________________________________ x.sub.k 0 1 2 3 4 5 6 y.sub.k 0 0 1 1 1 2 2 f.sub.k 0 1/3 2/3 1 4/3 5/3 2 (=1/3 x.sub.k) =0.333 =0.666 =1.333 =1.666 g.sub.k 1/2 1/2 3/2 3/2 3/2 5/2 5/2 (=y.sub.k +1/2) =0.5 =0.5 =1.5 =1.5 =1.5 =2.5 =2.5 ______________________________________
Referring to Table 1 and to FIG. 2 P.sub.0 is the starting point, with the coordinates (x.sub.0, y.sub.0) having the respective values (0, 0). The comparative value g.sub.0 is g.sub.0 =Y.sub.0 +1/2=0+0.5=0.5. The comparative value g.sub.0 (=0.5) is a Y coordinate of a comparative point c.sub.1 of a true value f.sub.1 on the line x.sub.1 =1 at requiring the next lattice point P.sub.1.
The true value f.sub.1 at x.sub.1 =1 is f.sub.1 =(1/3)x.sub.1 =1/3=0.333. In the case where f.sub.1&lt;g.sub.0, it is apparent from the equation (10) and FIG. 2 that y.sub.1 =y.sub.0 =0. Namely, the coordinates (x.sub.1,Y.sub.1) of the succeeding lattice point P.sub.1 from the point P.sub.0 to simulate the line y=(1/3)x.
Next, the comparative value g.sub.1 is determined to be g.sub.1 =y.sub.1 +1/2=0+0.5=0.5.
The coordinates (x.sub.2, y.sub.2) of the next lattice point P.sub.2 at x.sub.2 =2 must be determined. The true value f.sub.2 at x.sub.2 =2 is f.sub.2 =(1/3)x.sub.2 =(1/3)X.sub.2 2/3=0.666. In this case where f.sub.2 &gt;g.sub.1, it is apparent from the equation (11) and FIG. 2 that y.sub.2 =y.sub.1 +1=0+1=1. The comparative value g.sub.2 is determined to be g.sub.2 =y.sub.2 +1/2=1+0.5=1.5. It should be noted that the coordinates of the lattice points P.sub.3 through P.sub.5 at x.sub.3 (=3) x.sub.5 (=5) must be determined in the same manner as explained above and as shown in FIG. 2.
As can be seen from the above said explanation the straight line coordinates generator of the prior art requires a decimal point to ascertain the true value f.sub.k and the comparative value g.sub.k and further to compare the decimal values including decimal points of f.sub.k with g.sub.k. For these reasons, the straight line coordinates generator circuits must have analog circuits, for instance integrators, to process decimal points. However, it is well known that these analog circuits are complicated, expensive and very slow to process. Although there are some methods which use a microprocessor to process the intelligent functions in firmware, they have proven to be slower than using the analog circuits for processing.